{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Sum Swap LCCI"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #LCCI"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #hash-table #binary-search #sorting"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #哈希表 #二分查找 #排序"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: findSwapValues"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #交换和"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给定两个整数数组，请交换一对数值（每个数组中取一个数值），使得两个数组所有元素的和相等。</p>\n",
    "\n",
    "<p>返回一个数组，第一个元素是第一个数组中要交换的元素，第二个元素是第二个数组中要交换的元素。若有多个答案，返回任意一个均可。若无满足条件的数值，返回空数组。</p>\n",
    "\n",
    "<p><strong>示例:</strong></p>\n",
    "\n",
    "<pre><strong>输入:</strong> array1 = [4, 1, 2, 1, 1, 2], array2 = [3, 6, 3, 3]\n",
    "<strong>输出:</strong> [1, 3]\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例:</strong></p>\n",
    "\n",
    "<pre><strong>输入:</strong> array1 = <code>[1, 2, 3], array2 = [4, 5, 6]</code>\n",
    "<strong>输出: </strong>[]</pre>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= array1.length, array2.length &lt;= 100000</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [sum-swap-lcci](https://leetcode.cn/problems/sum-swap-lcci/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [sum-swap-lcci](https://leetcode.cn/problems/sum-swap-lcci/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = []"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findSwapValues(self, array1: List[int], array2: List[int]) -> List[int]:\n",
    "        s1=sum(array1)\n",
    "        s2=sum(array2)\n",
    "        target=s1-s2\n",
    "        if target%2!=0:return []\n",
    "        target/=2\n",
    "        dict1=set(array1)\n",
    "        dict2=set(array2)\n",
    "        for a in dict1:\n",
    "            if a-target in dict2:\n",
    "                return [a,int(a-target)]\n",
    "        return []"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findSwapValues(self, array1: List[int], array2: List[int]) -> List[int]:\n",
    "        sum1,sum2 = sum(array1),sum(array2)\n",
    "        # print(sum1,sum2)\n",
    "        target = sum1-sum2\n",
    "        # if target%2:return []\n",
    "        acc1 = set(array1)\n",
    "        acc2 = set(array2)\n",
    "        for c in acc2:\n",
    "            tmp = c+target/2\n",
    "            if tmp in acc1:\n",
    "                return [int(tmp),c]\n",
    "        return []\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findSwapValues(self, array1: List[int], array2: List[int]) -> List[int]:\n",
    "\n",
    "        # A-X=B\n",
    "        # A-a+b=B-b+a\n",
    "        # X=2a-2b\n",
    "\n",
    "        A=sum(array1)\n",
    "        B=sum(array2)\n",
    "        X=A-B \n",
    "\n",
    "        # print(X%2)\n",
    "        if X%2:\n",
    "            return []\n",
    "        else:\n",
    "            X=X//2\n",
    "            set1=set(array1)\n",
    "            set2=set(array2)\n",
    "            temp=None\n",
    "            \n",
    "            for i in set1:\n",
    "                if i-X in set2:\n",
    "                    temp=i\n",
    "                    break\n",
    "            # print(X)\n",
    "            if temp==None:\n",
    "                return []\n",
    "            else:\n",
    "                return [temp,temp-X]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findSwapValues(self, array1: List[int], array2: List[int]) -> List[int]:\n",
    "        diff = sum(array1) - sum(array2)\n",
    "        if diff % 2 != 0:\n",
    "            return []\n",
    "        set2 = set(array2)\n",
    "        for num1 in array1:\n",
    "            if num1 - diff // 2 in set2:\n",
    "                return [num1, num1 - diff // 2]\n",
    "        return []"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findSwapValues(self, array1: List[int], array2: List[int]) -> List[int]:\n",
    "      s1 = sum (array1)\n",
    "      s2 = sum (array2)\n",
    "      if (s1+s2)%2 != 0:\n",
    "        return []\n",
    "      d = (s1+s2)//2 - s1\n",
    "      a1 = set(array1)\n",
    "      a2 = set(array2)\n",
    "      for i in a1:\n",
    "        if i+d in a2:\n",
    "          return [i,i+d]\n",
    "      return []"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findSwapValues(self, array1: List[int], array2: List[int]) -> List[int]:\n",
    "        df = sum(array1) -sum(array2)\n",
    "        s = set(array2)\n",
    "        for i in array1:\n",
    "            if i - df/2 in s:\n",
    "                return [i,i-df/2]\n",
    "        return []"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findSwapValues(self, array1: List[int], array2: List[int]) -> List[int]:\n",
    "        sum_1 = sum(array1)\n",
    "        sum_2 = sum(array2)\n",
    "        if sum_1 == sum_2:\n",
    "            return []\n",
    "\n",
    "        target_sum = sum_1 + sum_2\n",
    "        if target_sum % 2 == 1:\n",
    "            return []\n",
    "        target_sum = target_sum//2\n",
    "\n",
    "        num_dict2 = {num: 1 for num in array2}\n",
    "        for ni in array1:\n",
    "            swap_num = target_sum + ni - sum_1\n",
    "            if swap_num in num_dict2:\n",
    "                return [ni, swap_num]\n",
    "        return []"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findSwapValues(self, array1: List[int], array2: List[int]) -> List[int]:\n",
    "        if (sum(array1)+sum(array2)) % 2:\n",
    "            return []\n",
    "        target_sum = (sum(array1) + sum(array2)) / 2 \n",
    "\n",
    "        target_dif = sum(array1) - target_sum\n",
    "        \n",
    "        # print(target_sum, target_dif)\n",
    "        arr2_set = set(array2)\n",
    "        for i in range(len(array1)):\n",
    "            if array1[i] - target_dif in arr2_set:\n",
    "                return [array1[i], array1[i] - target_dif]\n",
    "        \n",
    "        return []"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findSwapValues(self, array1: List[int], array2: List[int]) -> List[int]:\n",
    "        sum1=sum(array1)\n",
    "        sum2=sum(array2)\n",
    "\n",
    "        if (sum1+sum2)&1==1:return []\n",
    "\n",
    "        number=sum1-sum2\n",
    "        array1=set(array1)\n",
    "\n",
    "        for a2 in array2:\n",
    "            if number//2+a2 in array1:\n",
    "                return [number//2+a2,a2]\n",
    "        return []\n",
    "        \n",
    "        \n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findSwapValues(self, array1: List[int], array2: List[int]) -> List[int]:\n",
    "        s1, s2 = sum(array1), sum(array2)\n",
    "        set1, set2 = set(array1), set(array2)\n",
    "        \n",
    "        s = s1 - s2 if s1 > s2 else s2-s1\n",
    "\n",
    "        if s2 > s1:\n",
    "            for a in set2:\n",
    "                if a - (s/2) in set1:\n",
    "                    return [int(a - (s/2)), a]\n",
    "            return []\n",
    "        else:\n",
    "            for a in set1:\n",
    "                if a - (s/2) in set2:\n",
    "                    return [a, int(a - (s/2))]\n",
    "            return []"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findSwapValues(self, array1: List[int], array2: List[int]) -> List[int]:\n",
    "        diff = sum(array1) - sum(array2)\n",
    "        if diff % 2 != 0:\n",
    "            return []\n",
    "        diff //= 2\n",
    "        d = set(array2)\n",
    "        for num in array1:\n",
    "            if num - diff in d:\n",
    "                return [num, num - diff]\n",
    "        return []\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findSwapValues(self, array1: List[int], array2: List[int]) -> List[int]:\n",
    "        s1 = set(array1)\n",
    "        s2 = set(array2)\n",
    "        sum12 = sum(array1) + sum(array2)\n",
    "        if sum12 % 2 != 0:\n",
    "            return []\n",
    "        each = sum12 // 2\n",
    "        sum1 = sum(array1)\n",
    "        diff = sum1 - each\n",
    "        # if max(array1) - min(array2) < diff or min(array1) - max(array2) > diff:\n",
    "        #     return []\n",
    "        for i in s1:\n",
    "            if i - diff in s2:\n",
    "                return [i,i-diff]\n",
    "        return []"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findSwapValues(self, array1: List[int], array2: List[int]) -> List[int]:\n",
    "        if (sum(array1)+sum(array2)) % 2:\n",
    "            return []\n",
    "        target_sum = (sum(array1) + sum(array2)) / 2 \n",
    "\n",
    "        target_dif = sum(array1) - target_sum\n",
    "        \n",
    "        # print(target_sum, target_dif)\n",
    "        arr2_set = set(array2)\n",
    "        for i in range(len(array1)):\n",
    "            if array1[i] - target_dif in arr2_set:\n",
    "                return [array1[i], array1[i] - target_dif]\n",
    "        \n",
    "        return []"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import bisect\n",
    "class Solution:\n",
    "    def findSwapValues(self, array1: List[int], array2: List[int]) -> List[int]:\n",
    "        s1 = sum(array1)\n",
    "        s2 = sum(array2)\n",
    "        delta = s2 - s1\n",
    "        if delta % 2 == 1:\n",
    "            return []\n",
    "        delta //= 2\n",
    "        s = set(array2)\n",
    "        for num in array1:\n",
    "            if (num+delta) in s:\n",
    "                return [num,num+delta]\n",
    "        return []\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findSwapValues(self, array1: List[int], array2: List[int]) -> List[int]:\n",
    "        diff = sum(array1) - sum(array2)\n",
    "        if diff % 2 != 0:\n",
    "            return []\n",
    "        n = int(diff/2)\n",
    "        for i in set(array1):\n",
    "            j = i - n\n",
    "            if j in set(array2):\n",
    "                return [i,j]\n",
    "        return []\n",
    "        \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findSwapValues(self, array1: List[int], array2: List[int]) -> List[int]:\n",
    "        sum1 = sum(array1)\n",
    "        sum2 = sum(array2)\n",
    "        dif = sum1 - sum2\n",
    "        if dif % 2 == 1:\n",
    "            return []\n",
    "        diff = dif//2\n",
    "        s2 = set(array2)\n",
    "        for i in array1:\n",
    "            if i - diff in s2:\n",
    "                return [i,i-diff]\n",
    "        \n",
    "        return []"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findSwapValues(self, array1: List[int], array2: List[int]) -> List[int]:\n",
    "        sum1,sum2 = sum(array1),sum(array2)\n",
    "        # print(sum1,sum2)\n",
    "        target = sum1-sum2\n",
    "        if target%2:return []\n",
    "        acc1 = set(array1)\n",
    "        acc2 = set(array2)\n",
    "        for c in acc2:\n",
    "            tmp = c+target//2\n",
    "            if tmp in acc1:\n",
    "                return [int(tmp),c]\n",
    "        return []\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findSwapValues(self, array1: List[int], array2: List[int]) -> List[int]:\n",
    "        k = (sum(array1)-sum(array2))\n",
    "        if k%2:return list()\n",
    "        for num1 in set(array1):\n",
    "            if num1-k//2 in set(array2):\n",
    "                return [num1,num1-k//2]\n",
    "        return list()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "[4, 1, 2, 1, 1, 2]\n",
    "[3, 6, 3, 3]\n",
    "[1, 2, 3]\n",
    "[4, 5, 6]\n",
    "[1,4]\n",
    "[2,5]\n",
    "\n",
    "1 <= array1.length, array2.length <= 100000\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def findSwapValues(self, array1: List[int], array2: List[int]) -> List[int]:\n",
    "        sum1 = sum(array1)\n",
    "        sum2 = sum(array2)\n",
    "\n",
    "        # Calculate the target value that needs to be compensated\n",
    "        target = (sum1 - sum2) / 2\n",
    "\n",
    "        # If target is not an integer, there is no solution\n",
    "        if not target.is_integer():\n",
    "            return []\n",
    "\n",
    "        target = int(target)\n",
    "\n",
    "        # Create a set from array2 for constant time look-up\n",
    "        values = set(array2)\n",
    "\n",
    "        # Find a value in array1 where value - target is in array2\n",
    "        for value in array1:\n",
    "            if (value - target) in values:\n",
    "                return [value, value - target]\n",
    "\n",
    "        # No pair found\n",
    "        return []"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findSwapValues(self, array1: List[int], array2: List[int]) -> List[int]:\n",
    "        sum1, sum2 = sum(array1), sum(array2)\n",
    "        if (sum2 - sum1) % 2 == 1: return []\n",
    "\n",
    "        diff = (sum2 - sum1)//2\n",
    "        s2 = set(array2)\n",
    "        for i in array1:\n",
    "            if (diff + i) in s2:\n",
    "                return [i, diff + i]\n",
    "        return []\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findSwapValues(self, array1: List[int], array2: List[int]) -> List[int]:\n",
    "        sum_a = sum(array1) + sum(array2)\n",
    "        if sum_a % 2 == 1:\n",
    "            return []\n",
    "\n",
    "        diff = sum(array1) - sum_a // 2\n",
    "\n",
    "        array2_set = set(array2)\n",
    "\n",
    "        for x1 in array1:\n",
    "            if x1 - diff in array2_set:\n",
    "                return [x1, x1 - diff]\n",
    "        return []"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findSwapValues(self, array1: List[int], array2: List[int]) -> List[int]:\n",
    "        diff=sum(array1)-sum(array2)\n",
    "        if diff&1==1: return []\n",
    "        diff>>=1\n",
    "        s=set(array2)\n",
    "        for n in array1:\n",
    "            if n-diff in s: return [n,n-diff]\n",
    "        return []\n",
    "        \n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findSwapValues(self, array1: List[int], array2: List[int]) -> List[int]:\n",
    "        s1 = sum(array1)\n",
    "        s2 = sum(array2)\n",
    "        count2 = Counter(array2)\n",
    "        count1 = Counter(array1)\n",
    "        # s1 - x + y = s2 - y + x => x - y = (s1 - s2) / 2 => y = x - (s1 - s2) / 2 \n",
    "        d = (s1 - s2)\n",
    "        if d % 2:\n",
    "            return []\n",
    "        d = d // 2\n",
    "        for k in count1:\n",
    "            if k - d in count2:\n",
    "                return [k, k - d]\n",
    "        return []"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findSwapValues(self, array1: List[int], array2: List[int]) -> List[int]:\n",
    "        s1 = sum(array1)\n",
    "        s2 = sum(array2)\n",
    "        if (s1 - s2) % 2 == 1:\n",
    "            return []\n",
    "        delta = (s1 - s2) // 2\n",
    "        array2 = set(array2)\n",
    "        for i in range(len(array1)):\n",
    "            if array1[i] - delta in array2:\n",
    "                return [array1[i], array1[i] - delta]\n",
    "            if array1[i] + delta in array2:\n",
    "                return [array1[i], array1[i] + delta]\n",
    "        return []"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findSwapValues(self, array1: List[int], array2: List[int]) -> List[int]:\n",
    "        s1 = set(array1)\n",
    "        s2 = set(array2)\n",
    "        sum12 = sum(array1) + sum(array2)\n",
    "        if sum12 % 2 != 0:\n",
    "            return []\n",
    "        each = sum12 // 2\n",
    "        sum1 = sum(array1)\n",
    "        diff = sum1 - each\n",
    "        # if max(array1) - min(array2) < diff or min(array1) - max(array2) > diff:\n",
    "        #     return []\n",
    "        for i in s1:\n",
    "            if i - diff in s2:\n",
    "                return [i,i-diff]\n",
    "        return []"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findSwapValues(self, array1: List[int], array2: List[int]) -> List[int]:\n",
    "        s = sum(array1) + sum(array2)\n",
    "        if s % 2:\n",
    "            return []\n",
    "        t = s // 2 - sum(array1)\n",
    "        vis = set()\n",
    "        a2 = defaultdict(int)\n",
    "        for num in array2:\n",
    "            a2[num] += 1\n",
    "        \n",
    "        for num in array1:\n",
    "            if num not in vis:\n",
    "                if num + t in a2:\n",
    "                    return [num, num + t]\n",
    "                vis.add(num)\n",
    "        return []\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findSwapValues(self, array1: List[int], array2: List[int]) -> List[int]:\n",
    "        s1=sum(array1)\n",
    "        s2=sum(array2)\n",
    "        diff=(s1-s2)/2\n",
    "        arr2=set(array2)\n",
    "        for a in array1:\n",
    "            if a-diff in arr2:\n",
    "                return [a,a-diff]\n",
    "        return []\n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findSwapValues(self, array1: List[int], array2: List[int]) -> List[int]:\n",
    "        s1, s2 = set(array1), set(array2)\n",
    "        diff = sum(array1) - sum(array2)\n",
    "        if diff % 2 != 0:\n",
    "            return []\n",
    "        diff = diff // 2\n",
    "        for num1 in s1:\n",
    "            target = num1 - diff\n",
    "            if target in s2:\n",
    "                return [num1, target]\n",
    "        return []"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findSwapValues(self, array1: List[int], array2: List[int]) -> List[int]:\n",
    "        s1,s2=sum(array1),sum(array2)\n",
    "        diff=(s2-s1)/2\n",
    "        set1, set2 = set(array1), set(array2)\n",
    "        for i in set1:\n",
    "            if i+diff in set2:\n",
    "                return [i, i+diff]\n",
    "        return []"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findSwapValues(self, array1: List[int], array2: List[int]) -> List[int]:\n",
    "        sum1 = sum(array1)\n",
    "        sum2 = sum(array2)\n",
    "        target = sum1-sum2\n",
    "        array2 = set(array2)\n",
    "        for num1 in array1:\n",
    "            if (2*num1-target)/2 in array2:\n",
    "                return [num1,(2*num1-target)//2]\n",
    "        return []"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findSwapValues(self, array1: List[int], array2: List[int]) -> List[int]:\n",
    "        sum1,sum2 = sum(array1),sum(array2)\n",
    "        # print(sum1,sum2)\n",
    "        target = sum1-sum2\n",
    "        if target%2:return []\n",
    "        acc1 = set(array1)\n",
    "        acc2 = set(array2)\n",
    "        for c in acc2:\n",
    "            tmp = c+target//2\n",
    "            if tmp in acc1:\n",
    "                return [tmp,c]\n",
    "        return []\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findSwapValues(self, array1: List[int], array2: List[int]) -> List[int]:\n",
    "        # print(sum([4, 1, 2, 1, 1, 2]))\n",
    "        # print(sum([3, 6, 3, 3]))\n",
    "        # 相差 4\n",
    "        # print(sum([4, 3, 2, 1, 1, 2]))\n",
    "        # print(sum([3, 6, 1, 3]))\n",
    "        \n",
    "        diff = sum(array1) - sum(array2)\n",
    "        if diff & 1: return []\n",
    "        diff >>= 1\n",
    "        s2 = set(array2)\n",
    "        for a in array1:\n",
    "            if a - diff in s2:\n",
    "                return [a, a - diff]\n",
    "        return []        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findSwapValues(self, array1: List[int], array2: List[int]) -> List[int]:\n",
    "        sum1,sum2 = sum(array1),sum(array2)\n",
    "        # print(sum1,sum2)\n",
    "        target = sum1-sum2\n",
    "        if target%2:return []\n",
    "        acc1 = set(array1)\n",
    "        acc2 = set(array2)\n",
    "        for c in acc2:\n",
    "            tmp = c+target//2\n",
    "            if tmp in acc1:\n",
    "                return [tmp,c]\n",
    "        return []\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findSwapValues(self, array1: List[int], array2: List[int]) -> List[int]:\n",
    "        s1=sum(array1)\n",
    "        s2=sum(array2)\n",
    "        target=s1-s2\n",
    "        if target%2!=0:return []\n",
    "        target/=2\n",
    "        dict1=set(array1)\n",
    "        dict2=set(array2)\n",
    "        for a in dict1:\n",
    "            if a-target in dict2:\n",
    "                return [a,a-target]\n",
    "        return []"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findSwapValues(self, array1: List[int], array2: List[int]) -> List[int]:\n",
    "        sum1, sum2 = sum(array1), sum(array2)\n",
    "        if (sum1 + sum2) % 2:\n",
    "            return []\n",
    "        average = (sum1 + sum2) // 2\n",
    "        gap = sum1 - average\n",
    "        nums2 = set(array2)\n",
    "        for num in array1:\n",
    "            if num - gap in nums2:\n",
    "                return [num, num - gap]\n",
    "        return []\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findSwapValues(self, array1: List[int], array2: List[int]) -> List[int]:\n",
    "        s1,s2=sum(array1),sum(array2)\n",
    "        diff=(s2-s1)/2\n",
    "        set1, set2 = set(array1), set(array2)\n",
    "        for i in set1:\n",
    "            if i+diff in set2:\n",
    "                return [i, i+diff]\n",
    "        return []"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findSwapValues(self, array1: List[int], array2: List[int]) -> List[int]:\n",
    "        sum1 = sum(array1)\n",
    "        sum2 = sum(array2)\n",
    "        unique1 = sorted(list(set(array1)))\n",
    "        unique2 = sorted(list(set(array2)))\n",
    "\n",
    "\n",
    "        if (sum1 - sum2) % 2 == 1:\n",
    "            return []\n",
    "        diff = (sum1 - sum2) // 2\n",
    "\n",
    "        i, j = 0, 0\n",
    "        while i<len(unique1) and j < len(unique2):\n",
    "            e1 = unique1[i]\n",
    "            e2 = unique2[j]\n",
    "            \n",
    "            if e1 - e2 < diff:\n",
    "                i+=1\n",
    "            elif e1 - e2 > diff:\n",
    "                j+=1\n",
    "            else:\n",
    "                return [e1, e2]\n",
    "        return []"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def findSwapValues(self, array1: List[int],\n",
    "                       array2: List[int]) -> List[int]:\n",
    "        diff = sum(array1) - sum(array2)\n",
    "        if diff & 1: return []\n",
    "        diff >>= 1\n",
    "        s2 = set(array2)\n",
    "        for a in array1:\n",
    "            if a - diff in s2:\n",
    "                return [a, a - diff]\n",
    "        return []\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findSwapValues(self, array1: List[int], array2: List[int]) -> List[int]:\n",
    "        sum_1 = sum(array1)\n",
    "        sum_2 = sum(array2)\n",
    "        if sum_1 == sum_2:\n",
    "            return []\n",
    "\n",
    "        target_sum = sum_1 + sum_2\n",
    "        if target_sum % 2 == 1:\n",
    "            return []\n",
    "        target_sum = target_sum//2\n",
    "\n",
    "        # if len(array1) > len(array2):\n",
    "        #     array1, sum_1, array2, sum_2 =  array2, sum_2, array1, sum_1\n",
    "\n",
    "        num_dict2 = {num: 1 for num in array2}\n",
    "        sum_delta = target_sum - sum_1\n",
    "        for ni in array1:\n",
    "            swap_num = sum_delta + ni\n",
    "            if swap_num in num_dict2:\n",
    "                return [ni, swap_num]\n",
    "        return []"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findSwapValues(self, array1: List[int], array2: List[int]) -> List[int]:\n",
    "        # sum1 = sum(array1)\n",
    "        # sum2 = sum(array2)\n",
    "        # if((sum1+sum2)%2==1):\n",
    "        #     return []\n",
    "        # tar = (sum1+sum2)>>1\n",
    "        # cha = tar-sum1\n",
    "        # s2 = set(array2)\n",
    "        # for i in array1:\n",
    "        #     if(i+cha in array2):\n",
    "        #         return [i,i+cha]\n",
    "        # return []\n",
    "\n",
    "        sum1, sum2 = sum(array1), sum(array2)\n",
    "        if (sum1 + sum2) % 2:\n",
    "            return []\n",
    "        average = (sum1 + sum2) // 2\n",
    "        gap = sum1 - average\n",
    "        nums2 = set(array2)\n",
    "        for num in array1:\n",
    "            if num - gap in nums2:\n",
    "                return [num, num - gap]\n",
    "        return []\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findSwapValues(self, array1: List[int], array2: List[int]) -> List[int]:\n",
    "        n=sum(array1)-sum(array2)\n",
    "        if n%2==1:\n",
    "            return[]\n",
    "        n=n//2\n",
    "        s2=set(array2)\n",
    "        for num in array1:\n",
    "            if num-n in s2:\n",
    "                return [num,num-n]\n",
    "        return []"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findSwapValues(self, array1: List[int], array2: List[int]) -> List[int]:\n",
    "        sum_1 = sum(array1)\n",
    "        sum_2 = sum(array2)\n",
    "        target_sum = sum_1 + sum_2\n",
    "        if sum_1 == sum_2 or target_sum % 2 == 1:\n",
    "            return []\n",
    "        target_sum = target_sum//2\n",
    "\n",
    "        target_sum % 2 == 1\n",
    "        num_dict2 = {num: 1 for num in array2}\n",
    "        sum_delta = target_sum - sum_1\n",
    "        for ni in set(array1):\n",
    "            swap_num = sum_delta + ni\n",
    "            if swap_num in num_dict2:\n",
    "                return [ni, swap_num]\n",
    "        return []"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findSwapValues(self, array1: List[int], array2: List[int]) -> List[int]:\n",
    "        s1,s2=sum(array1),sum(array2)\n",
    "        diff=(s2-s1)/2\n",
    "        set2 = set(array2)\n",
    "        for i in array1:\n",
    "            if i+diff in set2:\n",
    "                return [i, i+diff]\n",
    "        return []"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "\n",
    "class Solution:\n",
    "    def findSwapValues(self, array1: List[int], array2: List[int]) -> List[int]:\n",
    "        sum1, sum2 = sum(array1), sum(array2)\n",
    "        diff = sum1 - sum2\n",
    "\n",
    "        # 判断差值是否为偶数，只有当差值为偶数时，才可能找到合适的 x 和 y\n",
    "        if diff % 2 != 0:\n",
    "            return []\n",
    "\n",
    "        diff //= 2  # x - y 的值\n",
    "\n",
    "        # 使用集合来加速查找操作\n",
    "        set2 = set(array2)\n",
    "\n",
    "        # 遍历 array1，找到一个值 x，使得 x - y = diff\n",
    "        for x in array1:\n",
    "            y = x - diff\n",
    "            if y in set2:\n",
    "                return [x, y]\n",
    "\n",
    "        return []\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findSwapValues(self, array1: List[int], array2: List[int]) -> List[int]:\n",
    "        diff = sum(array1) - sum(array2)\n",
    "        if diff & 1: return []\n",
    "        diff >>= 1\n",
    "        s2 = set(array2)\n",
    "        for a in array1:\n",
    "            if a - diff in s2:\n",
    "                return [a, a - diff]\n",
    "        return []\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findSwapValues(self, array1: List[int], array2: List[int]) -> List[int]:\n",
    "        diff = (sum(array1) - sum(array2)) / 2\n",
    "        # if diff % 2 != 0:\n",
    "        #     return []\n",
    "\n",
    "        sorted_array1 = sorted(array1)\n",
    "        sorted_array2 = sorted(array2)\n",
    "        i = j = 0\n",
    "\n",
    "        print(\"diff: \", diff)\n",
    "\n",
    "        while i < len(sorted_array1) and j < len(sorted_array2):\n",
    "            cur_diff = sorted_array1[i] - sorted_array2[j]\n",
    "            # print(\"array1: \", sorted_array1[i], sorted_array2[j])\n",
    "            # print(\"cur_diff: \", cur_diff)\n",
    "            if cur_diff == diff:\n",
    "                return [sorted_array1[i], sorted_array2[j]]\n",
    "            elif cur_diff > diff:\n",
    "                j += 1\n",
    "            else:\n",
    "                i += 1\n",
    "        \n",
    "        return []"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findSwapValues(self, array1: List[int], array2: List[int]) -> List[int]:\n",
    "        sum1,sum2 = sum(array1),sum(array2)\n",
    "        # print(sum1,sum2)\n",
    "        target = sum1-sum2\n",
    "        if target%2:return []\n",
    "        acc1 = set(array1)\n",
    "        acc2 = set(array2)\n",
    "        for c in acc2:\n",
    "            tmp = c+target//2\n",
    "            if tmp in acc1:\n",
    "                return [int(tmp),c]\n",
    "        return []\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findSwapValues(self, array1: List[int], array2: List[int]) -> List[int]:\n",
    "        s1 = set(array1)\n",
    "        s2 = set(array2)\n",
    "        sum12 = sum(array1) + sum(array2)\n",
    "        if sum12 % 2 != 0:\n",
    "            return []\n",
    "        each = sum12 // 2\n",
    "        sum1 = sum(array1)\n",
    "        diff = sum1 - each\n",
    "        if max(s1) - min(s2) < diff or min(s1) - max(s2) > diff:\n",
    "            return []\n",
    "        for i in s1:\n",
    "            if i - diff in s2:\n",
    "                return [i,i-diff]\n",
    "        return []"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findSwapValues(self, array1: List[int], array2: List[int]) -> List[int]:\n",
    "        s1 = sum(array1)\n",
    "        s2 = sum(array2)\n",
    "        if abs(s1 - s2) % 2 == 1:\n",
    "            return []\n",
    "        d = (s1 - s2) // 2\n",
    "        s = set(array1)\n",
    "        for x in set(array2):\n",
    "            if x + d in s:\n",
    "                return [x+d, x]\n",
    "        return []\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findSwapValues(self, array1: List[int], array2: List[int]) -> List[int]:\n",
    "\n",
    "\n",
    "        sum_1 = sum(array1)\n",
    "        sum_2 = sum(array2)\n",
    "        array2.sort()\n",
    "        max_len = len(array2)-1\n",
    "        def check(t_a):\n",
    "            left=0\n",
    "            right = max_len\n",
    "            t_sum = sum_2+2*t_a\n",
    "            \n",
    "            while left<right:\n",
    "                mid = left+(right-left)//2\n",
    "                \n",
    "                if (t:=sum_1+ 2*array2[mid]) == t_sum:\n",
    "                    return array2[mid]\n",
    "                elif t>t_sum:\n",
    "                    right-=1\n",
    "                else:\n",
    "                    left+=1\n",
    "            \n",
    "        visit = set()\n",
    "        for a_1 in array1:\n",
    "            if a_1 in visit:\n",
    "                continue\n",
    "            visit.add(a_1)\n",
    "            if t:= check(a_1):\n",
    "                return [a_1, t]\n",
    "        return []"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findSwapValues(self, array1: List[int], array2: List[int]) -> List[int]:\n",
    "        re = []\n",
    "        sum1 = sum(array1)\n",
    "        sum2 = sum(array2)\n",
    "        swapFlag = False\n",
    "        if sum1>sum2:\n",
    "            sum1, sum2 = sum2, sum1\n",
    "            array1, array2 = array2, array1\n",
    "            swapFlag = True\n",
    "        det = (sum2-sum1)/2\n",
    "        if (sum2-sum1)%2:\n",
    "            return []\n",
    "        array1.sort()\n",
    "        array2.sort()\n",
    "        flag = False\n",
    "        for i, pi in enumerate(array1):\n",
    "            for pj in range(len(array2)-1, -1, -1):\n",
    "                T = array2[pj] -pi\n",
    "                if T > det:\n",
    "                    continue\n",
    "                if T==det:\n",
    "                    if swapFlag:\n",
    "                        re = [array2[pj], pi]\n",
    "                    else:\n",
    "                        re = [pi, array2[pj]]\n",
    "                    flag = True\n",
    "                    break\n",
    "                if T<det:\n",
    "                    break\n",
    "            if flag:\n",
    "                break\n",
    "        return re"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findSwapValues(self, array1: List[int], array2: List[int]) -> List[int]:\n",
    "        sum1=sum(array1)\n",
    "        sum2=sum(array2)\n",
    "        dif=sum2-sum1\n",
    "        print(dif)\n",
    "        if dif%2:\n",
    "            return []\n",
    "        dif//=2\n",
    "        array1=set(array1)\n",
    "        array2=set(array2)\n",
    "        for x in array1:\n",
    "            y=x+dif\n",
    "            if y in array2:\n",
    "                return[x,y]\n",
    "        return []"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
